{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Subarray Ranges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subArrayRanges"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组范围和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 。<code>nums</code> 中，子数组的 <strong>范围</strong> 是子数组中最大元素和最小元素的差值。</p>\n",
    "\n",
    "<p>返回 <code>nums</code> 中 <strong>所有</strong> 子数组范围的 <strong>和</strong> <em>。</em></p>\n",
    "\n",
    "<p>子数组是数组中一个连续 <strong>非空</strong> 的元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>nums 的 6 个子数组如下所示：\n",
    "[1]，范围 = 最大 - 最小 = 1 - 1 = 0 \n",
    "[2]，范围 = 2 - 2 = 0\n",
    "[3]，范围 = 3 - 3 = 0\n",
    "[1,2]，范围 = 2 - 1 = 1\n",
    "[2,3]，范围 = 3 - 2 = 1\n",
    "[1,2,3]，范围 = 3 - 1 = 2\n",
    "所有范围的和是 0 + 0 + 0 + 1 + 1 + 2 = 4</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,3,3]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>nums 的 6 个子数组如下所示：\n",
    "[1]，范围 = 最大 - 最小 = 1 - 1 = 0\n",
    "[3]，范围 = 3 - 3 = 0\n",
    "[3]，范围 = 3 - 3 = 0\n",
    "[1,3]，范围 = 3 - 1 = 2\n",
    "[3,3]，范围 = 3 - 3 = 0\n",
    "[1,3,3]，范围 = 3 - 1 = 2\n",
    "所有范围的和是 0 + 0 + 0 + 2 + 0 + 2 = 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,-2,-3,4,1]\n",
    "<strong>输出：</strong>59\n",
    "<strong>解释：</strong>nums 中所有子数组范围的和是 59\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以设计一种时间复杂度为 <code>O(n)</code> 的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-subarray-ranges](https://leetcode.cn/problems/sum-of-subarray-ranges/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-subarray-ranges](https://leetcode.cn/problems/sum-of-subarray-ranges/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[1,3,3]', '[4,-2,-3,4,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        stk = [-1]\n",
    "        sum = 0\n",
    "        for i, v in enumerate(nums+[inf]):\n",
    "            while len(stk)>1 and nums[stk[-1]] <= v:\n",
    "                j = stk.pop()\n",
    "                sum += nums[j]*(i-j)*(j-stk[-1]) \n",
    "            stk.append(i)\n",
    "        stk = [-1]\n",
    "        for i, v in enumerate(nums+[-inf]):\n",
    "            while len(stk)>1 and nums[stk[-1]] >= v:\n",
    "                j = stk.pop()\n",
    "                sum -= nums[j]*(i-j)*(j-stk[-1]) \n",
    "            stk.append(i)\n",
    "        return sum\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp = 0\n",
    "            min_num = nums[i]\n",
    "            max_num = nums[i]\n",
    "            for j in range(i, len(nums)):\n",
    "                if nums[j] > max_num:\n",
    "                    max_num = nums[j]\n",
    "                if nums[j] < min_num:\n",
    "                    min_num = nums[j]\n",
    "                res += (max_num - min_num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        # 1 <= nums.length <= 1000 ;; 随便暴力好吧\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            mi = ma = nums[i]\n",
    "            for j in range(i, n):\n",
    "                mi = min(mi, nums[j])\n",
    "                ma = max(ma, nums[j])\n",
    "                ans += ma - mi\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        sum1 = 0\n",
    "        # sum of maximum number in each subarray - sum of minimum number in each subarray\n",
    "        stack = [-1]\n",
    "        for i, num in enumerate(nums+[inf]):\n",
    "            while len(stack) > 1 and nums[stack[-1]] < num:\n",
    "                idx = stack.pop()\n",
    "                left = stack[-1]\n",
    "                right = i\n",
    "                sum1 += (idx - left) * (right - idx) * nums[idx]\n",
    "            stack.append(i)\n",
    "        \n",
    "        sum2 = 0\n",
    "        stack = [-1]\n",
    "        for i, num in enumerate(nums+[-inf]):\n",
    "            while len(stack) > 1 and nums[stack[-1]] > num:\n",
    "                idx = stack.pop()\n",
    "                left = stack[-1]\n",
    "                right = i\n",
    "                sum2 += (idx - left) * (right - idx) * nums[idx]\n",
    "            stack.append(i)\n",
    "\n",
    "        return sum1 - sum2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        nums_extended = [float(\"-inf\")] + nums + [float(\"-inf\")]\n",
    "        stack = collections.deque()\n",
    "        for i, v in enumerate(nums_extended):\n",
    "            while len(stack) != 0 and v < nums_extended[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                result -= nums_extended[idx] * (i - idx) * (idx - stack[-1])\n",
    "            stack.append(i)\n",
    "        \n",
    "        nums_extended = [float(\"inf\")] + nums + [float(\"inf\")]\n",
    "        stack = collections.deque()\n",
    "        for i, v in enumerate(nums_extended):\n",
    "            while len(stack) != 0 and v > nums_extended[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                result += nums_extended[idx] * (i - idx) * (idx - stack[-1])\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        # nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            max_val = nums[i]\n",
    "            min_val = nums[i]\n",
    "            for j in range(i+1, n):\n",
    "                nums_j = nums[j]\n",
    "                if nums_j > max_val:\n",
    "                    max_val = nums_j\n",
    "                if nums_j < min_val:\n",
    "                    min_val = nums_j\n",
    "                ans += max_val - min_val    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        nums_extended = [-inf] + nums + [-inf]\n",
    "        stack = collections.deque()\n",
    "        for i, v in enumerate(nums_extended):\n",
    "            while stack and v < nums_extended[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                result -= nums_extended[idx] * (i - idx) * (idx - stack[-1])\n",
    "            stack.append(i)\n",
    "        \n",
    "        nums_extended = [inf] + nums + [inf]\n",
    "        stack = collections.deque()\n",
    "        for i, v in enumerate(nums_extended):\n",
    "            while stack and v > nums_extended[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                result += nums_extended[idx] * (i - idx) * (idx - stack[-1])\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        \n",
    "        def getRes(nums):\n",
    "            nonlocal n\n",
    "            st = []\n",
    "            left = [-1 for i in range(0, n)]\n",
    "            right = [n for i in range(0, n)]\n",
    "            res = 0\n",
    "            for i in range(0, n):\n",
    "                while st and nums[st[-1]] <= nums[i]:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            \n",
    "            st = []\n",
    "            for i in range(n-1,-1,-1):\n",
    "                while st and nums[st[-1]] < nums[i]:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    right[i] = st[-1]\n",
    "                st.append(i)\n",
    "            \n",
    "            for i in range(0, n):\n",
    "                res = res + nums[i] * (i - left[i]) * (right[i] - i)\n",
    "            return res\n",
    "\n",
    "\n",
    "        temp = getRes(nums)\n",
    "        for i in range(0, n):\n",
    "            nums[i] = -nums[i]\n",
    "        return temp + getRes(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            mn, mx = inf, -inf\n",
    "            for j in range(i, n):\n",
    "                mn = min(mn, nums[j])\n",
    "                mx = max(mx, nums[j])\n",
    "                ans += mx - mn\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        st = [-1]\n",
    "        for i, x in enumerate(nums + [-inf]):\n",
    "            while len(st) > 1 and nums[st[-1]] > x:\n",
    "                j = st.pop()\n",
    "                ans -= nums[j] * (i - j) * (j - st[-1])\n",
    "            st.append(i)\n",
    "        st = [-1]\n",
    "        for i, x in enumerate(nums + [inf]):\n",
    "            while len(st) > 1 and nums[st[-1]] <= x:\n",
    "                j = st.pop()\n",
    "                ans += nums[j] * (i - j) * (j - st[-1])\n",
    "            st.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            mx = mn = x\n",
    "            for j in range(i + 1, n):\n",
    "                mx = max(mx, nums[j])\n",
    "                mn = min(mn, nums[j])\n",
    "                ans += mx - mn\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_contribute(self, nums):\n",
    "        n = len(nums)\n",
    "        left = [-1] * n   # 左侧大于的元素位置，默认为-1\n",
    "        right = [n] * n  # 右侧大于等于的元素位置，默认为右边界的右边\n",
    "        st = []     # 单调栈，只有小于才能放入\n",
    "        for i, n in enumerate(nums):\n",
    "            while st and n >= nums[st[-1]]: # 如果大于等于顶层\n",
    "                right[st.pop()] = i   # 对于顶层来说，现在试图加入的就是右侧第一个大于等于它的\n",
    "            # 现在要么小于顶层，要么栈已经空了\n",
    "            if st:                  # 如果栈没空\n",
    "                left[i] = st[-1]        # 左侧第一个大于的就是它\n",
    "            st.append(i)\n",
    "        ans = 0\n",
    "        for i, (l, r, num) in enumerate(zip(left, right, nums)):\n",
    "            ans += num * (r - i) * (i - l)\n",
    "        return ans\n",
    "\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        mx = self.get_contribute(nums)\n",
    "        nums = [*map(neg, nums)]\n",
    "        mn = self.get_contribute(nums)\n",
    "        return mx + mn\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        result = 0\n",
    "        nums_extended = [float(\"-inf\")] + nums + [float(\"-inf\")]\n",
    "        stack = collections.deque()\n",
    "        for i, v in enumerate(nums_extended):\n",
    "            while len(stack) != 0 and v < nums_extended[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                result -= nums_extended[idx] * (i - idx) * (idx - stack[-1])\n",
    "            stack.append(i)\n",
    "        \n",
    "        nums_extended = [float(\"inf\")] + nums + [float(\"inf\")]\n",
    "        stack = collections.deque()\n",
    "        for i, v in enumerate(nums_extended):\n",
    "            while len(stack) != 0 and v > nums_extended[stack[-1]]:\n",
    "                idx = stack.pop()\n",
    "                result += nums_extended[idx] * (i - idx) * (idx - stack[-1])\n",
    "            stack.append(i)\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            submax = submin = nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                submax = max(nums[j],submax)\n",
    "                submin = min(nums[j],submin)\n",
    "                ans += submax-submin\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "       n = len(nums)\n",
    "       leftMax = [-1] * n\n",
    "       rightMax = [n] * n\n",
    "       leftMin = [-1] * n\n",
    "       rightMin = [n] * n\n",
    "       stMax = []\n",
    "       stMin = []\n",
    "       for i in range(n):\n",
    "          while stMax and nums[stMax[-1]] <= nums[i]:\n",
    "             rightMax[stMax.pop()] = i\n",
    "          if stMax:\n",
    "             leftMax[i] = stMax[-1]\n",
    "          stMax.append(i)\n",
    "\n",
    "          while stMin and nums[stMin[-1]] >= nums[i]:\n",
    "             rightMin[stMin.pop()] = i\n",
    "          if stMin:\n",
    "             leftMin[i] = stMin[-1]\n",
    "          stMin.append(i)\n",
    "\n",
    "       res = 0\n",
    "       for i in range(n):\n",
    "          res += nums[i] * ((rightMax[i] - i) * (i - leftMax[i]) - (rightMin[i] - i) * (i - leftMin[i]))\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        sum = 0\n",
    "        for i in range(n):\n",
    "            Max = nums[i]\n",
    "            Min = nums[i]\n",
    "            for j in range(i, n):\n",
    "                if Max < nums[j]:\n",
    "                    Max = nums[j]\n",
    "                if Min > nums[j]:\n",
    "                    Min  = nums[j]\n",
    "                sum += Max - Min\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            mx = mn = nums[i]\n",
    "            for j in range(i + 1, len(nums)):\n",
    "                if nums[j] > mx:\n",
    "                    mx = nums[j]\n",
    "                elif nums[j] < mn:\n",
    "                    mn = nums[j]\n",
    "                ans += mx - mn\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(n):\n",
    "            minVal, maxVal = inf, -inf\n",
    "            for j in range(i, n):\n",
    "                minVal = min(minVal, nums[j])\n",
    "                maxVal = max(maxVal, nums[j])\n",
    "                ans += maxVal - minVal\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_contribute(self, nums):\n",
    "        n = len(nums)\n",
    "        left = [-1] * n   # 左侧大于的元素位置，默认为-1\n",
    "        right = [n] * n  # 右侧大于等于的元素位置，默认为右边界的右边\n",
    "        st = []     # 单调栈，只有小于才能放入\n",
    "        for i, n in enumerate(nums):\n",
    "            while st and n >= nums[st[-1]]: # 如果大于等于顶层\n",
    "                top = st.pop()  # 对于顶层来说，现在试图加入的就是右侧第一个大于等于它的\n",
    "                right[top] = i\n",
    "            # 现在要么小于顶层，要么栈已经空了\n",
    "            if st:                  # 如果栈没空\n",
    "                left[i] = st[-1]        # 左侧第一个大于的就是它\n",
    "            st.append(i)\n",
    "        ans = 0\n",
    "        for i, (l, r, num) in enumerate(zip(left, right, nums)):\n",
    "            ans += num * (r - i) * (i - l)\n",
    "        return ans\n",
    "\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        mx = self.get_contribute(nums)\n",
    "        nums = [*map(neg, nums)]\n",
    "        mn = self.get_contribute(nums)\n",
    "        print(mx, mn)\n",
    "        return mx + mn\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            maxn = float(\"-Inf\")\n",
    "            minn = float(\"Inf\")\n",
    "            for j in range(i, n):\n",
    "                maxn = max(maxn, nums[j])\n",
    "                minn = min(minn, nums[j])\n",
    "                res += (maxn - minn)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for right, num in enumerate(nums + [float(\"inf\")]):\n",
    "            while stack and nums[stack[-1]] < num:\n",
    "                cur = stack.pop()\n",
    "                left = -1 if not stack else stack[-1]\n",
    "                res += (cur - left) * (right - cur) * nums[cur]\n",
    "            stack.append(right)\n",
    "\n",
    "        stack = []\n",
    "        for right, num in enumerate(nums + [float(\"-inf\")]):\n",
    "            while stack and nums[stack[-1]] > num:\n",
    "                cur = stack.pop()\n",
    "                left = -1 if not stack else stack[-1]\n",
    "                res -= (cur - left) * (right - cur) * nums[cur]\n",
    "            stack.append(right)\n",
    "        return res\n",
    "\n",
    "\n",
    "# 基础知识1： 设nums[j],nums[k]为nums[i]左右最近的比nums[i]小的值\n",
    "#             则以nums[i]为最小值的子数组共有(i - j) * (k - i)个 （不超过j,k范围且包含i的子数组总数）\n",
    "#             最大值也同理\n",
    "\n",
    "# 基础知识2： 子数组的范围和可以表示为所有子数组最大值之和 减去 子数组最小值之和（简单数学推导）\n",
    "\n",
    "# 由1、2可知：如果能创建两个数组minLeft和minRight，下标i的值保存基础知识1中j和k的下标\n",
    "#             则(i - minLeft[i]) * (minRight[i] - j)即为以nums[i]为最小值的子数组总数\n",
    "#             用此值再乘以 nums[i] 即可得到nums[i]为最小值的子数组的最小值之和\n",
    "#             对每一个 0 < i < len - 1 做此操作并叠加最小值之和，即可得到整个数组的子数组最小值之和\n",
    "#             最大值同理，由基础知识2即可求得子数组范围和\n",
    "\n",
    "# 因此，本题的难点在于：如何构造minLeft和minRight数组(maxLeft, maxRight)\n",
    "\n",
    "# 以minLeft为例，利用单调栈构造数组，具体如下：\n",
    "# 1. 从左到右遍历nums数组\n",
    "# 2. 对于遍历到的nums[i]，执行出栈(pop)直到：\n",
    "#     1) 栈空\n",
    "#     2) 栈顶(top)小于nums[i]\n",
    "# 此时，可记录minLeft[i]的值为栈顶元素 或 -1 (栈空时)，然后将i压入栈中(push)\n",
    "\n",
    "# 经此操作，可以构造出minLeft数组；类似也可构造maxLeft,minRight,maxRight\n",
    "\n",
    "# 为保证最大值/最小值的唯一性，在出现相同的值时，以下标的大小作为第二判断标准，下标小的认为是更小的值\n",
    "\n",
    "# 子数组范围的和等价于 （子数组的最大值的和）-（子数组的最小值的和）。\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def subArrayRanges(self, nums: List[int]) -> int:\n",
    "#         res = 0\n",
    "#         stack = []\n",
    "#         # 子数组的最大值的和\n",
    "#         for right, num in enumerate(nums + [float(\"inf\")]):\n",
    "#             while stack and nums[stack[-1]] < num:\n",
    "#                 cur = stack.pop()\n",
    "#                 left = -1 if not stack else stack[-1]\n",
    "#                 res += (cur - left) * (right - cur) * nums[cur]\n",
    "#             stack.append(right)\n",
    "#             print(stack)\n",
    "\n",
    "#         stack = []\n",
    "#         # 子数组的最小值的和\n",
    "#         for right, num in enumerate(nums + [float(\"-inf\")]):\n",
    "#             while stack and nums[stack[-1]] > num:\n",
    "#                 cur = stack.pop()\n",
    "#                 left = -1 if not stack else stack[-1]\n",
    "#                 res -= (cur - left) * (right - cur) * nums[cur]\n",
    "#             stack.append(right)\n",
    "#         return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n, res = len(nums), 0\n",
    "        for i in range(n):\n",
    "            mn, mx = nums[i], nums[i]\n",
    "            for j in range(i, n):\n",
    "                mn = min(mn, nums[j])\n",
    "                mx = max(mx, nums[j])\n",
    "                res += mx - mn\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums) \n",
    "        ans = 0\n",
    "        for l in range(n-1):\n",
    "            lv = mx = mn = nums[l]\n",
    "            for r in range(l+1, n):\n",
    "                rv = nums[r]\n",
    "                if rv > mx:\n",
    "                    mx = rv\n",
    "                if rv < mn:\n",
    "                    mn = rv\n",
    "                ans += mx - mn\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre = [-1] * n\n",
    "        nxt = [n] * n\n",
    "\n",
    "        s = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while s and x < arr[s[-1]]:\n",
    "                nxt[s.pop()] = i\n",
    "            s.append(i)\n",
    "\n",
    "        # 从右往左遍历\n",
    "        s = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while s and arr[i] <= arr[s[-1]]:\n",
    "                pre[s.pop()] = i\n",
    "            s.append(i)\n",
    "\n",
    "        ans = 0\n",
    "        for i, x in enumerate(arr):\n",
    "            ans -= (i-pre[i])*(nxt[i]-i)*x\n",
    "        \n",
    "        pre = [-1] * n\n",
    "        nxt = [n] * n\n",
    "        s = []\n",
    "        for i, x in enumerate(arr):\n",
    "            while s and x > arr[s[-1]]:\n",
    "                nxt[s.pop()] = i\n",
    "            s.append(i)\n",
    "\n",
    "        # 从右往左遍历\n",
    "        s = []\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while s and arr[i] >= arr[s[-1]]:\n",
    "                pre[s.pop()] = i\n",
    "            s.append(i)\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            ans += (i-pre[i])*(nxt[i]-i)*x\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            left, right = inf, -inf\n",
    "            for j in range(i,len(nums)):\n",
    "                left = min(left,nums[j])\n",
    "                right = max(right,nums[j])\n",
    "                ans += right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n,res = len(nums),0\n",
    "        left,right = [-1]*n,[n]*n\n",
    "        sta = []\n",
    "        for i,num in enumerate(nums):\n",
    "            while sta and nums[sta[-1]]<num:\n",
    "                right[sta[-1]]=i\n",
    "                sta.pop()\n",
    "            if sta: left[i]=sta[-1]\n",
    "            sta.append(i)\n",
    "        for i,(num,l,r) in enumerate(zip(nums,left,right)):\n",
    "            res += num*(i-l)*(r-i)\n",
    "        left,right = [-1]*n,[n]*n\n",
    "        sta = []\n",
    "        for i,num in enumerate(nums):\n",
    "            while sta and nums[sta[-1]]>num:\n",
    "                right[sta[-1]]=i\n",
    "                sta.pop()\n",
    "            if sta: left[i]=sta[-1]\n",
    "            sta.append(i)\n",
    "        for i,(num,l,r) in enumerate(zip(nums,left,right)):\n",
    "            res -= num*(i-l)*(r-i)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n-1):\n",
    "            mn,mx = nums[i],nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                if mn > nums[j]:\n",
    "                    mn = nums[j]\n",
    "                if mx < nums[j]:\n",
    "                    mx = nums[j]\n",
    "                ans += mx-mn\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            minv = 1<<30\n",
    "            maxv = -minv\n",
    "            for j in range(i, n):\n",
    "                maxv = max(maxv, max(nums[i], nums[j]))\n",
    "                minv = min(minv, min(nums[i], nums[j]))\n",
    "                ret += maxv - minv                \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def sumSubarrayMins(arr: List[int]) -> int:\n",
    "            n = len(arr)\n",
    "            left, right = [-1] * n, [n] * n\n",
    "            st = []\n",
    "            for i, x in enumerate(arr):\n",
    "                while st and arr[st[-1]] <= x:\n",
    "                    right[st.pop()] = i\n",
    "                if st:\n",
    "                    left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            res = 0\n",
    "            for i, x in enumerate(arr):\n",
    "                res += x * (i - left[i]) * (right[i] - i)\n",
    "            return res\n",
    "        r1 = sumSubarrayMins(nums)\n",
    "        nums = [-x for x in nums]\n",
    "        r2 = sumSubarrayMins(nums)\n",
    "        return r1 + r2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            max_i=nums[i]\n",
    "            min_i=nums[i]\n",
    "            for j in range(i+1, n):\n",
    "                max_i=max(max_i,nums[j])\n",
    "                min_i=min(min_i,nums[j])\n",
    "                ans+=max_i-min_i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def mono_stack_smaller(arr):\n",
    "            n = len(arr)\n",
    "            left = [-1] * n # 左侧<=x的坐标 \n",
    "            right = [n] * n #右侧<x的坐标\n",
    "            st = []\n",
    "            for i,x in enumerate(arr):\n",
    "                while st and arr[st[-1]] > x:\n",
    "                    right[st.pop()] = i\n",
    "                if st:\n",
    "                    left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            return left, right\n",
    "        \n",
    "        def mono_stack_greater(arr):\n",
    "            n = len(arr)\n",
    "            left = [-1] * n # 左侧>=x的坐标 \n",
    "            right = [n] * n #右侧>x的坐标\n",
    "            st = []\n",
    "            for i,x in enumerate(arr):\n",
    "                while st and arr[st[-1]] < x:\n",
    "                    right[st.pop()] = i\n",
    "                if st:\n",
    "                    left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            return left, right\n",
    "\n",
    "        ans = 0\n",
    "        ls,rs = mono_stack_smaller(nums)\n",
    "        lg,rg = mono_stack_greater(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            ans += x * (i-lg[i]) * (rg[i] -i)\n",
    "            ans -= x * (i-ls[i]) * (rs[i] -i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans, stack = 0, []\n",
    "        for i, num in enumerate(nums + [inf]):\n",
    "            while stack and nums[stack[-1]] < num:\n",
    "                # 栈顶元素作为最大值的时代结束了, 它作为最大值的区间为它的前一个坐标到当前把它弹出的坐标 \n",
    "                # 左边选一个作为左端点，右边选一个作为右端点，这个区间上它都是最大值\n",
    "                # 故出现次数为 组合数 C_l1 * C_r1 \n",
    "                ans += nums[(j:=stack.pop())] * (i - j) * (j - (stack[-1] if stack else -1))\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i, num in enumerate(nums + [-inf]):\n",
    "            while stack and nums[stack[-1]] > num:\n",
    "                ans -= nums[(j:=stack.pop())] * (i - j) * (j - (stack[-1] if stack else -1))\n",
    "            stack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            min_val=nums[i]\n",
    "            max_val=nums[i]\n",
    "            for j in range(i+1,n):\n",
    "                min_val=min(nums[j],min_val)\n",
    "                max_val=max(nums[j],max_val)\n",
    "                ans+=max_val-min_val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        result_1 = result_2 = 0\n",
    "        stack = []\n",
    "        lenn = len(nums)\n",
    "        L = [0] * lenn\n",
    "        R = [0] * lenn\n",
    "\n",
    "        for j in range(2):\n",
    "            stack = []\n",
    "            L = [0] * lenn\n",
    "            R = [0] * lenn\n",
    "            for i in range(lenn):\n",
    "                if j == 0:\n",
    "                    while stack and nums[stack[-1]] > nums[i]:\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    while stack and nums[stack[-1]] < nums[i]:\n",
    "                        stack.pop()                    \n",
    "                if not stack:\n",
    "                    L[i] = -1\n",
    "                else:\n",
    "                    L[i] = stack[-1]\n",
    "                stack.append(i)\n",
    "\n",
    "            stack = []\n",
    "            for i in range(lenn-1, -1, -1):\n",
    "                if j == 0:\n",
    "                    while stack and nums[stack[-1]] >= nums[i]:\n",
    "                        stack.pop()\n",
    "                else:\n",
    "                    while stack and nums[stack[-1]] <= nums[i]:\n",
    "                        stack.pop()                    \n",
    "                if not stack:\n",
    "                    R[i] = lenn\n",
    "                else:\n",
    "                    R[i] = stack[-1]\n",
    "                stack.append(i)\n",
    "\n",
    "            for i in range(lenn):\n",
    "                if j == 0:\n",
    "                    result_1 += nums[i] * (i - L[i]) * (R[i] - i)\n",
    "                else:\n",
    "                    result_2 += nums[i] * (i - L[i]) * (R[i] - i)\n",
    "\n",
    "        return (result_2 - result_1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans,size=0,len(nums)\n",
    "        for i,num1 in enumerate(nums):\n",
    "            mintemp,maxtemp=inf,-inf\n",
    "            for j ,num2 in enumerate(nums[i:]):\n",
    "                mintemp=min(mintemp,num2)\n",
    "                maxtemp=max(maxtemp,num2)\n",
    "                ans+=maxtemp-mintemp\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        s = MonoStack(nums)\n",
    "        def ok(l,r,nums):\n",
    "            res = 0\n",
    "            for i,x in enumerate(nums):\n",
    "                res += (i-l[i])*(r[i]-i)*x\n",
    "            return res\n",
    "        mxl,mxr = s.get_bound_as_max_left_over_and_right_stop()\n",
    "        mil,mir = s.get_bound_as_min_left_over_and_right_stop()\n",
    "        return ok(mxl,mxr,nums)-ok(mil,mir,nums)\n",
    "\n",
    "\n",
    "\n",
    "class MonoStack:\n",
    "    # 单调栈，计算每个数作为最大/最小值值能到的前后边界。时/空复杂度O(n)\n",
    "    # 注意，这里每个方法前/后遇到相同值的情况都是相反的，\n",
    "    # 如果需要真实的前后边界，需要使用get_true的方法/或者调用两个函数，然后一边取l,一边取r\n",
    "    def __init__(self, a):\n",
    "        self.a = a\n",
    "\n",
    "    def get_bound_as_max_left_over_and_right_stop(self):\n",
    "        \"\"\"使用单调递减栈，计算\n",
    "        每个值作为最大值，前后能到达的边界（寻找左右第一个比它小的值）\n",
    "        这里向左会越过相同值，向右会在相同值停下来。（防止重复计算区间）\n",
    "        初始值为-1/n。\n",
    "        \"\"\"\n",
    "        a, n = self.a, len(self.a)\n",
    "        l, r, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(a):\n",
    "            while st and a[st[-1]] <= v:\n",
    "                r[st.pop()] = i\n",
    "            if st:\n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return l, r\n",
    "\n",
    "    def get_bound_as_max_left_stop_and_right_over(self):\n",
    "        \"\"\"使用单调递减栈，计算\n",
    "        每个值作为最大值，前后能到达的边界（寻找左右第一个比它小的值）\n",
    "        这里向左会遇到相同值停下，向右会越过相同值。（防止重复计算区间）\n",
    "        初始值为-1/n。\n",
    "        \"\"\"\n",
    "        a, n = self.a, len(self.a)\n",
    "        l, r, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(a):\n",
    "            while st and a[st[-1]] < v:\n",
    "                r[st.pop()] = i\n",
    "            if st:\n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return l, r\n",
    "\n",
    "    def get_true_bound_as_max(self):\n",
    "        # 使用单调递减栈，计算两边的真实边界(越过相同值)\n",
    "        l, _ = self.get_bound_as_max_left_over_and_right_stop()\n",
    "        _, r = self.get_bound_as_max_left_stop_and_right_over()\n",
    "        return l, r\n",
    "\n",
    "    def get_bound_as_min_left_over_and_right_stop(self):\n",
    "        \"\"\"使用单调递增栈，计算\n",
    "        每个值作为最小值，前后能到达的边界（寻找左右第一个比它大的值）\n",
    "        这里向左会越过相同值，向右会在相同值停下来。（防止重复计算区间）\n",
    "        初始值为-1/n。\n",
    "        \"\"\"\n",
    "        a, n = self.a, len(self.a)\n",
    "        l, r, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(a):\n",
    "            while st and a[st[-1]] >= v:\n",
    "                r[st.pop()] = i\n",
    "            if st:\n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return l, r\n",
    "\n",
    "    def get_bound_as_min_left_stop_and_right_over(self):\n",
    "        \"\"\"使用单调递增栈，计算\n",
    "        每个值作为最小值，前后能到达的边界（寻找左右第一个比它大的值）\n",
    "        这里向左会遇到相同值停下，向右会越过相同值。（防止重复计算区间）\n",
    "        初始值为-1/n。\n",
    "        \"\"\"\n",
    "        a, n = self.a, len(self.a)\n",
    "        l, r, st = [-1] * n, [n] * n, []\n",
    "        for i, v in enumerate(a):\n",
    "            while st and a[st[-1]] > v:\n",
    "                r[st.pop()] = i\n",
    "            if st:\n",
    "                l[i] = st[-1]\n",
    "            st.append(i)\n",
    "        return l, r\n",
    "\n",
    "    def get_true_bound_as_min(self):\n",
    "        # 使用单调递增栈，计算两边的真实边界(越过相同值)\n",
    "        l, _ = self.get_bound_as_min_left_over_and_right_stop()\n",
    "        _, r = self.get_bound_as_min_left_stop_and_right_over()\n",
    "        return l, r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        st = []\n",
    "        Left_min = [-1] * n\n",
    "        Right_min = [n] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and nums[st[-1]] >= x:\n",
    "                Right_min[st.pop()] = i\n",
    "            if st:\n",
    "                Left_min[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        \n",
    "        st = []\n",
    "        Left_max = [-1] * n\n",
    "        Right_max = [n] * n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while st and nums[st[-1]] <= nums[i]:\n",
    "                Left_max[st.pop()] = i\n",
    "            if st:\n",
    "                Right_max[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        \n",
    "        sum_min = 0\n",
    "        sum_max = 0\n",
    "        for i, (l, r, x) in enumerate(zip(Left_min, Right_min, nums)):\n",
    "            sum_min += (i - l) * (r - i) * x\n",
    "        for i, (l, r, x) in enumerate(zip(Left_max, Right_max, nums)):\n",
    "            sum_max += (i - l) * (r - i) * x\n",
    "\n",
    "\n",
    "        return sum_max - sum_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans, n = 0, len(nums)\n",
    "\n",
    "        for i in range(n):\n",
    "            minVal, maxVal = inf, -inf\n",
    "            for j in range(i, n):\n",
    "                minVal = min(minVal, nums[j])\n",
    "                maxVal = max(maxVal, nums[j])\n",
    "                ans += maxVal - minVal\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        # 贡献法  某数x如果是子数组最大值就会为答案贡献x，如果是最小值就会贡献-x\n",
    "        # 单调栈 保证栈内升序，当一个数被弹，说明它的右边界出现了，而左边界就是栈内的前一个 即可求得作为最大值的贡献\n",
    "        # 再弄个栈，存负数，用一样的逻辑可求出最小值的栈\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        mnst,mxst=[-1],[-1]\n",
    "        nums.append(math.inf) # 为了让最后元素都弹栈，同时让第1个元素可以正确计算到\n",
    "        for i,x in enumerate(nums): # 考虑最大值边界\n",
    "            while nums[mxst[-1]]<x: # 将比 x 小的都弹栈就知道了 x的左边界，同时因为出现了更大的x，原栈顶的右边界也出现了\n",
    "                j=mxst.pop()\n",
    "                ans+=nums[j]*(i-j)*(j-mxst[-1])\n",
    "                # print(\"mx:\",nums[j],(i-j)*(j-mxst[-1]) )      \n",
    "            mxst.append(i)\n",
    "        nums[-1]=-math.inf\n",
    "        for i,x in enumerate(nums):\n",
    "            while nums[mnst[-1]]>x:\n",
    "                j=mnst.pop()\n",
    "                ans-=nums[j]*(i-j)*(j-mnst[-1])\n",
    "                # print(\"mn:\",nums[j],(i-j)*(j-mnst[-1]) )   \n",
    "            mnst.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left_max = [-1]*n\n",
    "        left_min = [-1]*n\n",
    "        right_max = [n]*n\n",
    "        right_min = [n]*n\n",
    "        up_stk = []\n",
    "        down_stk = []\n",
    "        for i, v in enumerate(nums):\n",
    "            while up_stk and nums[up_stk[-1]] > v:\n",
    "                e = up_stk.pop()\n",
    "                right_min[e] = i\n",
    "            if up_stk:\n",
    "               left_min[i] = up_stk[-1]\n",
    "            up_stk.append(i)\n",
    "\n",
    "            while down_stk and nums[down_stk[-1]] <= v:\n",
    "                e = down_stk.pop()\n",
    "                right_max[e] = i\n",
    "            if down_stk:\n",
    "                left_max[i] = down_stk[-1]\n",
    "            down_stk.append(i)\n",
    "\n",
    "        return sum(\n",
    "            (i - left_max[i])*(right_max[i] - i)*v - (i - left_min[i])*(right_min[i] - i)*v\n",
    "            for i, v in enumerate(nums)\n",
    "        )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        # 动态规划\n",
    "        m = len(nums)\n",
    "        big = nums[:]\n",
    "        small = nums[:]\n",
    "        ans = 0\n",
    "        for i in range(1, m+1): #长度为1~m\n",
    "            for j in range(m+1-i): # 长度为i时，子数组的范围为i~j\n",
    "                big[j] = max(big[j], nums[j+i-1])\n",
    "                small[j] = min(small[j], nums[j+i-1])\n",
    "            ans += sum(big[:m+1-i])-sum(small[:m+1-i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        minStack = [] # monotonic decreasing stack\n",
    "        maxStack = [] # monotonic increasing stack\n",
    "        minNums = [float(\"-inf\")] + nums + [float(\"-inf\")]\n",
    "        maxNums = [float(\"inf\")] + nums + [float(\"inf\")]\n",
    "\n",
    "        for i in range(n+2):\n",
    "            while minStack and minNums[minStack[-1]] > minNums[i]:\n",
    "                j = minStack.pop()\n",
    "                ans -= minNums[j] * (i - j) * (j - minStack[-1])\n",
    "            minStack.append(i)\n",
    "\n",
    "            while maxStack and maxNums[maxStack[-1]] < maxNums[i]:\n",
    "                j = maxStack.pop()\n",
    "                ans += maxNums[j] * (i - j) * (j - maxStack[-1])\n",
    "            maxStack.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "\n",
    "        def caltotal(nums: List[int]):\n",
    "            st =[]\n",
    "            n= len(nums)\n",
    "            left = [-1]*n\n",
    "            right = [n]*n\n",
    "            ans = 0 \n",
    "\n",
    "            for i ,x in enumerate(nums):\n",
    "                while st and nums[st[-1]]<=x:\n",
    "                    right[st.pop()] =i\n",
    "                if st:left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            for i ,x in enumerate(nums):\n",
    "                ans +=x*(i-left[i])*(right[i]-i)\n",
    "            return ans\n",
    "            \n",
    "        res=0\n",
    "        rnums = list(map(lambda x:-x,nums))\n",
    "        ans = caltotal(nums)+caltotal(rnums)\n",
    "        return ans\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        preMin, preMax = [-1, 0], [-1, 0]\n",
    "        n = len(nums)\n",
    "        for i in range(1, n):\n",
    "            while preMin[-1] >= 0 and nums[preMin[-1]] >= nums[i]:\n",
    "                prev = preMin.pop()\n",
    "                ans -= nums[prev] * (prev - preMin[-1]) * (i - prev)\n",
    "            preMin.append(i)\n",
    "\n",
    "            while preMax[-1] >= 0 and nums[preMax[-1]] <= nums[i]:\n",
    "                prev = preMax.pop()\n",
    "                ans += nums[prev] * (prev - preMax[-1]) * (i - prev)\n",
    "            preMax.append(i)\n",
    "\n",
    "        for i in range(1, len(preMin)):\n",
    "            ans -= nums[preMin[i]] * (preMin[i] - preMin[i-1]) * (n - preMin[i])\n",
    "\n",
    "        for i in range(1, len(preMax)):\n",
    "            ans +=  nums[preMax[i]] * (preMax[i] - preMax[i-1]) * (n - preMax[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "\n",
    "        st = []\n",
    "        Left_min = [-1] * n\n",
    "        Right_min = [n] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and nums[st[-1]] >= x:\n",
    "                Right_min[st.pop()] = i\n",
    "            if st:\n",
    "                Left_min[i] = st[-1]\n",
    "            st.append(i)\n",
    "        \n",
    "        \n",
    "        st = []\n",
    "        Left_max = [-1] * n\n",
    "        Right_max = [n] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            while st and nums[st[-1]] <= x:\n",
    "                Right_max[st.pop()] = i\n",
    "            if st:\n",
    "                Left_max[i] = st[-1]\n",
    "            st.append(i)\n",
    "\n",
    "        \n",
    "        sum_min = 0\n",
    "        sum_max = 0\n",
    "        for i, (l, r, x) in enumerate(zip(Left_min, Right_min, nums)):\n",
    "            sum_min += (i - l) * (r - i) * x\n",
    "        for i, (l, r, x) in enumerate(zip(Left_max, Right_max, nums)):\n",
    "            sum_max += (i - l) * (r - i) * x\n",
    "\n",
    "\n",
    "        return sum_max - sum_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        dp = [0] * length\n",
    "        maxls = [0] * length\n",
    "        minls = [0] * length\n",
    "        for i in range(length-1,-1,-1):\n",
    "            maxls[i],minls[i] = nums[i],nums[i]\n",
    "            tmp = 0\n",
    "            for j in range(i+1,length):\n",
    "                last_max = maxls[j]\n",
    "                maxls[j] = max(maxls[j],maxls[i])\n",
    "                tmp+= maxls[j] - last_max\n",
    "\n",
    "                last_min = minls[j]\n",
    "                minls[j] = min(minls[j],minls[i])\n",
    "                tmp+=  last_min-minls[j]\n",
    "\n",
    "            if i+1!=length:\n",
    "                dp[i]=dp[i+1]+tmp\n",
    "        return sum(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        nums_len = len(nums)\n",
    "        ans = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            min_, max_ = num,num\n",
    "            for j in range(i+1, nums_len):\n",
    "                v = nums[j]\n",
    "                if v<min_:\n",
    "                    min_=v\n",
    "                if v > max_:\n",
    "                    max_ = v\n",
    "                ans+= max_-min_\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            mx = mi = nums[i]\n",
    "            for j in range(i + 1, n):\n",
    "                if nums[j] > mx:\n",
    "                    mx = nums[j]\n",
    "                elif nums[j] < mi:\n",
    "                    mi = nums[j]\n",
    "                ans += mx - mi\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            max_val, min_val = -inf, inf\n",
    "            for j in range(i, len(nums)):\n",
    "                max_val = max(nums[j], max_val)\n",
    "                min_val = min(nums[j], min_val)\n",
    "                #print(\"max: \", max_val, \"min: \", min_val)\n",
    "                ans += max_val - min_val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, v in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] > v:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        mn = sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr))\n",
    "\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, v in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] < v:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[stack[-1]] <= arr[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        mx = sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr))\n",
    "        return mx - mn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def solve(nums):\n",
    "            n = len(nums)\n",
    "            left = [-1] * n\n",
    "            right = [n] * n\n",
    "            st = [-1]\n",
    "\n",
    "            for i, v in enumerate(nums):\n",
    "                while len(st) > 1 and nums[st[-1]] <= v:\n",
    "                    right[st[-1]] = i\n",
    "                    st.pop()\n",
    "\n",
    "                left[i] = st[-1]\n",
    "                st.append(i)\n",
    "\n",
    "            ans = 0\n",
    "            for i, v in enumerate(nums):\n",
    "                ans += (i - left[i]) * (right[i] - i) * v\n",
    "\n",
    "            return ans\n",
    "        \n",
    "\n",
    "        ans = solve(nums)\n",
    "        nums = [-v for v in nums]\n",
    "        return ans + solve(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        \n",
    "           \n",
    "        ans = 0\n",
    "            \n",
    "        st = [-1]\n",
    "        for i,x in enumerate(nums + [-inf]):\n",
    "            while len(st) > 1 and nums[st[-1]] > x:\n",
    "                j = st.pop()\n",
    "                ans -= nums[j] * (j - st[-1]) * (i - j)\n",
    "            st.append(i)\n",
    "        st = [-1]\n",
    "        for i,x in enumerate(nums + [inf]):\n",
    "            while len(st) > 1 and nums[st[-1]] <= x:\n",
    "                j = st.pop()\n",
    "                ans += nums[j] * (j - st[-1]) * (i - j)\n",
    "            st.append(i)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        st,left,right = [],[-1]*n,[n]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            while st and nums[st[-1]] < x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ans = sum((r-i)*(i-l)*x for i,(x,l,r) in enumerate(zip(nums,left,right)))\n",
    "        st,left,right = [],[-1]*n,[n]*n\n",
    "        for i,x in enumerate(nums):\n",
    "            while st and nums[st[-1]] > x:\n",
    "                right[st.pop()] = i\n",
    "            if st: left[i] = st[-1]\n",
    "            st.append(i)\n",
    "        ans -= sum((r-i)*(i-l)*x for i,(x,l,r) in enumerate(zip(nums,left,right)))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minleft,maxleft = [0]*n,[0]*n\n",
    "        minstack,maxstack = [],[]\n",
    "        for i,v in enumerate(nums):   #记录左侧最小最大\n",
    "            while minstack and nums[minstack[-1]] > v:\n",
    "                minstack.pop()\n",
    "            minleft[i] = minstack[-1] if minstack else -1\n",
    "            minstack.append(i)\n",
    "            while maxstack and nums[maxstack[-1]] <= v:\n",
    "                maxstack.pop()\n",
    "            maxleft[i] = maxstack[-1] if maxstack else -1\n",
    "            maxstack.append(i)\n",
    "        \n",
    "        minright,maxright = [0]*n,[0]*n\n",
    "        minstack,maxstack = [],[]\n",
    "        for i in range(n-1,-1,-1):   #记录右侧最小最大\n",
    "            v = nums[i]\n",
    "            while minstack and nums[minstack[-1]] >= v:\n",
    "                minstack.pop()\n",
    "            minright[i] = minstack[-1] if minstack else n\n",
    "            minstack.append(i)\n",
    "            while maxstack and nums[maxstack[-1]] < v:\n",
    "                maxstack.pop()\n",
    "            maxright[i] = maxstack[-1] if maxstack else n\n",
    "            maxstack.append(i)\n",
    "        s1 = s2 = 0\n",
    "        for i in range(n):\n",
    "            s1 += (maxright[i]-i)*(i-maxleft[i])*nums[i]\n",
    "            s2 += (minright[i]-i)*(i-minleft[i])*nums[i]\n",
    "\n",
    "        return s1-s2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def f(nums):\n",
    "            stk = []\n",
    "            n = len(nums)\n",
    "            left = [-1] * n\n",
    "            right = [n] * n\n",
    "            for i, v in enumerate(nums):\n",
    "                while stk and nums[stk[-1]] <= v:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    left[i] = stk[-1]\n",
    "                stk.append(i)\n",
    "            stk = []\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                while stk and nums[stk[-1]] < nums[i]:\n",
    "                    stk.pop()\n",
    "                if stk:\n",
    "                    right[i] = stk[-1]\n",
    "                stk.append(i)\n",
    "            return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(nums))\n",
    "\n",
    "        mx = f(nums)\n",
    "        mi = f([-v for v in nums])\n",
    "        return mx + mi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minstk, maxstk = [], []\n",
    "        minleft, minright = [-1]*n, [n]*n\n",
    "        maxleft, maxright = [-1]*n, [n]*n\n",
    "        ans = 0\n",
    "        for i,v in enumerate(nums):\n",
    "            while minstk and v<nums[minstk[-1]]:\n",
    "                minright[minstk[-1]] = i\n",
    "                minstk.pop()\n",
    "            if minstk:\n",
    "                minleft[i] = minstk[-1]\n",
    "            minstk.append(i)\n",
    "\n",
    "            while maxstk and v>=nums[maxstk[-1]]:\n",
    "                maxright[maxstk[-1]] = i\n",
    "                maxstk.pop()\n",
    "            if maxstk:\n",
    "                maxleft[i] = maxstk[-1]\n",
    "            maxstk.append(i)\n",
    "        for i in range(n):\n",
    "            ans += nums[i] * ((maxright[i]-i)*(i-maxleft[i])-(minright[i]-i)*(i-minleft[i]))\n",
    "        return ans \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        a = [-inf] + nums + [-inf]\n",
    "        stk = []\n",
    "        for i,v in enumerate(a):\n",
    "            while stk and a[stk[-1]] >= v:\n",
    "                base = stk.pop()\n",
    "                if stk:\n",
    "                    left = stk[-1]\n",
    "                    ans -= (i-base) * (base-left) *a[base]\n",
    "            stk.append(i)\n",
    "\n",
    "        b = [inf] + nums + [inf]\n",
    "        stk = []\n",
    "        for i,v in enumerate(b):\n",
    "            while stk and b[stk[-1]] <= v:\n",
    "                base = stk.pop()\n",
    "                if stk:\n",
    "                    left = stk[-1]\n",
    "                    ans += (i-base) * (base-left) *a[base]\n",
    "            stk.append(i)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        st1 = []\n",
    "        st2 = []\n",
    "        n = len(nums)\n",
    "        a = [-1] * n\n",
    "        b = [n] * n\n",
    "        c= [-1] * n\n",
    "        d = [n] * n\n",
    "        for i in range(n):\n",
    "            \n",
    "            while st1 and nums[i] >= nums[st1[-1]]:\n",
    "                b[st1.pop()] = i\n",
    "            if st1:\n",
    "                a[i] = st1[-1]\n",
    "            while st2 and nums[i] < nums[st2[-1]]:\n",
    "                d[st2.pop()] = i\n",
    "            if st2:\n",
    "                c[i] = st2[-1] \n",
    "            st1.append(i)\n",
    "            st2.append(i)\n",
    "        res = 0\n",
    "        for q,w,e,r,x,i in zip(a,b,c,d,nums,range(n)):\n",
    "            t1 = (i-q) * (w-i)\n",
    "            t2 = (i-e) * (r-i)\n",
    "            res += t1 * x - t2 * x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def helper(nums: List[int]) -> int:   \n",
    "            \"\"\"O(N) iterates over nums array to find left array and right array\"\"\"\n",
    "            n = len(nums)\n",
    "            left, right = [-1]*n, [n]*n\n",
    "            stack = []\n",
    "\n",
    "            for i in range(n):\n",
    "                while stack and nums[i] >= nums[stack[-1]]:\n",
    "                    right[stack.pop()] = i \n",
    "                    \n",
    "                if stack:\n",
    "                    left[i] = stack[-1]\n",
    "                \n",
    "                stack.append(i)\n",
    "            \n",
    "            total = 0\n",
    "            for i, num in enumerate(nums):\n",
    "                total += num * (i-left[i]) * (right[i]-i)\n",
    "            \n",
    "            return total \n",
    "\n",
    "        negNums = [-num for num in nums]\n",
    "        ans = helper(nums) + helper(negNums)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def sumSubarrayMins(arr: List[int]) -> int:\n",
    "            n = len(arr)\n",
    "            left, right = [-1] * n, [n] * n\n",
    "            st = []\n",
    "            for i, x in enumerate(arr):\n",
    "                while st and arr[st[-1]] <= x:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    left[i] = st[-1]\n",
    "                st.append(i)\n",
    "            st = []\n",
    "            for i in range(n - 1, -1, -1):\n",
    "                while st and arr[st[-1]] < arr[i]:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    right[i] = st[-1]\n",
    "                st.append(i)\n",
    "            res = 0\n",
    "            for i, x in enumerate(arr):\n",
    "                res += x * (i - left[i]) * (right[i] - i)\n",
    "            return res\n",
    "        r1 = sumSubarrayMins(nums)\n",
    "        nums = [-x for x in nums]\n",
    "        r2 = sumSubarrayMins(nums)\n",
    "        return r1 + r2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        def cal(nums):\n",
    "            n = len(nums)\n",
    "            left = [-1] * n\n",
    "            right = [n] * n\n",
    "            st = []\n",
    "            for i,x in enumerate(nums):\n",
    "                while st and nums[st[-1]] <= x:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    left[i] = st[-1]\n",
    "                st.append(i)\n",
    "\n",
    "            st = []\n",
    "            for i in range(n-1,-1,-1):\n",
    "                while st and nums[st[-1]] < nums[i]:\n",
    "                    st.pop()\n",
    "                if st:\n",
    "                    right[i] = st[-1]\n",
    "                st.append(i)\n",
    "            ans = 0\n",
    "            for i,(x,l,r) in enumerate(zip(nums,left,right)):\n",
    "                ans += x * (i - l) * (r - i)\n",
    "            return ans\n",
    "\n",
    "        ans = cal(nums)\n",
    "        temp = []\n",
    "        for num in nums:\n",
    "            temp.append(-num) # 所有元素取反作为最小值的贡献\n",
    "        \n",
    "        return ans + cal(temp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        \n",
    "        n = len(nums)\n",
    "        st1 = [[0] * 11 for _ in range(n)]\n",
    "        st2 = [[0] * 11 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            st1[i][0] = nums[i]\n",
    "            st2[i][0] = nums[i]\n",
    "        l = 1\n",
    "        for j in range(1, 11):\n",
    "            for i in range(n):\n",
    "                st1[i][j] = max(st1[i][j-1], st1[min(i+l, n-1)][j-1])\n",
    "                st2[i][j] = min(st2[i][j-1], st2[min(i+l, n-1)][j-1])\n",
    "            l *= 2\n",
    "        ans = 0\n",
    "        lg = [int(math.log(l, 2)) for l in range(1, 1002)]\n",
    "        lg.insert(0, 0)\n",
    "        p = [int(pow(2, x)) for x in range(11)]\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                l = i - j + 1\n",
    "                x = lg[l]\n",
    "                y = p[x]\n",
    "                mn = min(st2[j][x], st2[i-y+1][x])\n",
    "                mx = max(st1[j][x], st1[i-y+1][x])\n",
    "                ans += mx - mn \n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, v in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] > v:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[stack[-1]] >= arr[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        mn = sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr))\n",
    "\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i, v in enumerate(arr):\n",
    "            while stack and arr[stack[-1]] < v:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                left[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "        \n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and arr[stack[-1]] <= arr[i]:\n",
    "                stack.pop()\n",
    "            if stack:\n",
    "                right[i] = stack[-1]\n",
    "            stack.append(i)\n",
    "\n",
    "        mx = sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr))\n",
    "        return mx - mn\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # 初始化最大最小值 哈希表\n",
    "        max_dict = collections.defaultdict(int)\n",
    "        min_dict = collections.defaultdict(int)\n",
    "        for i in range(n):\n",
    "            max_dict[i] = -inf\n",
    "            min_dict[i] = inf\n",
    "        ans = 0\n",
    "        # 遍历子数组\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                # print([j,i]) debug 用 i总是单调增的，起点不一样\n",
    "                # 只要记录不同开始位置对应的最大最小值就可以\n",
    "                max_dict[j] = max(max_dict[j], nums[i-1])\n",
    "                min_dict[j] = min(min_dict[j], nums[i-1])\n",
    "                if i != j + 1:\n",
    "                    # 当数组中不止一个元素\n",
    "                    ans += (max_dict[j] - min_dict[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        minLeft,maxLeft,minRight,maxRight = [0] * n,[0] * n,[0] * n,[0] * n\n",
    "        minStack,maxStack = [],[]\n",
    "        for i in range(n):\n",
    "            while minStack and nums[minStack[-1]] > nums[i]:\n",
    "                minStack.pop()\n",
    "            minLeft[i] = minStack[-1] if minStack else -1\n",
    "            minStack.append(i)\n",
    "            while maxStack and nums[maxStack[-1]] < nums[i]:\n",
    "                maxStack.pop()\n",
    "            maxLeft[i] = maxStack[-1] if maxStack else -1\n",
    "            maxStack.append(i)\n",
    "        minStack,maxStack = [],[]\n",
    "        for i in range(n-1,-1,-1):\n",
    "            while minStack and nums[minStack[-1]] >= nums[i]:\n",
    "                minStack.pop()\n",
    "            minRight[i] = minStack[-1] if minStack else n\n",
    "            minStack.append(i)\n",
    "            while maxStack and nums[maxStack[-1]] <= nums[i]:\n",
    "                maxStack.pop()\n",
    "            maxRight[i] = maxStack[-1] if maxStack else n\n",
    "            maxStack.append(i)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            res -= (i - minLeft[i]) * (minRight[i] - i) * nums[i]\n",
    "            res += (i - maxLeft[i]) * (maxRight[i] - i) * nums[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n, res = len(nums), 0\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] >= nums[i]:\n",
    "                right[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] > nums[i]:\n",
    "                left[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        for i in range(n):\n",
    "            a, b = i - left[i], right[i] - i\n",
    "            res -= a * b * nums[i]\n",
    "\n",
    "        left, right = [-1] * n, [n] * n\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            while stack and nums[stack[-1]] <= nums[i]:\n",
    "                right[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        stack = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stack and nums[stack[-1]] < nums[i]:\n",
    "                left[stack.pop()] = i\n",
    "            stack.append(i)\n",
    "        for i in range(n):\n",
    "            a, b = i - left[i], right[i] - i\n",
    "            res += a * b * nums[i]\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        left = [0] * n\n",
    "        right = [0] * n \n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stk and x > nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[i] >= nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            else:\n",
    "                right[i] = n\n",
    "            stk.append(i)\n",
    "        max_sum = 0\n",
    "        for i in range(n):\n",
    "            max_sum += ((right[i] - left[i] - 1) + (right[i] - i - 1) * (i - left[i] - 1)) * nums[i]\n",
    "\n",
    "        left = [0] * n\n",
    "        right = [0] * n \n",
    "        stk = []\n",
    "        for i, x in enumerate(nums):\n",
    "            while stk and x < nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                left[i] = stk[-1]\n",
    "            else:\n",
    "                left[i] = -1\n",
    "            stk.append(i)\n",
    "        stk = []\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            while stk and nums[i] <= nums[stk[-1]]:\n",
    "                stk.pop()\n",
    "            if stk:\n",
    "                right[i] = stk[-1]\n",
    "            else:\n",
    "                right[i] = n\n",
    "            stk.append(i)\n",
    "        min_sum = 0\n",
    "        for i in range(n):\n",
    "            min_sum += ((right[i] - left[i] - 1) + (right[i] - i - 1) * (i - left[i] - 1)) * nums[i]\n",
    "        return max_sum - min_sum\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subArrayRanges(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        st1=[]\n",
    "        g=[[0,0] for _ in range(n)]\n",
    "        f=[[0,0] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            while st1:\n",
    "                if nums[st1[-1]]>nums[i]:\n",
    "                    cur=st1.pop()\n",
    "                    g[cur][1]=i-cur-1\n",
    "                else:\n",
    "                    g[i][0]=i-st1[-1]-1\n",
    "                    st1.append(i)\n",
    "                    break\n",
    "            if not st1:\n",
    "                st1.append(i)\n",
    "                g[i][0]=i\n",
    "                continue\n",
    "        while st1:\n",
    "            cur=st1.pop()\n",
    "            g[cur][1]=n-cur-1\n",
    "        \n",
    "        for i in range(n):\n",
    "            while st1:\n",
    "                if nums[st1[-1]]<nums[i]:\n",
    "                    cur=st1.pop()\n",
    "                    f[cur][1]=i-cur-1\n",
    "                else:\n",
    "                    f[i][0]=i-st1[-1]-1\n",
    "                    st1.append(i)\n",
    "                    break\n",
    "            if not st1:\n",
    "                st1.append(i)\n",
    "                f[i][0]=i\n",
    "                continue\n",
    "        while st1:\n",
    "            cur=st1.pop()\n",
    "            f[cur][1]=n-cur-1\n",
    "        for i in range(n):\n",
    "            left1=g[i][0]\n",
    "            right1=g[i][1]\n",
    "            left2=f[i][0]\n",
    "            right2=f[i][1]\n",
    "            ans-=nums[i]*(left1*right1 + left1+right1)\n",
    "            ans+=nums[i]*(left2*right2+left2+right2)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "                \n",
    "                       \n",
    "                \n",
    "                \n",
    "                \n",
    "            \n",
    "\n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
